﻿#pragma once

#include <iostream>
#include <vector>
#include <time.h>
#include <assert.h>
#include <thread>
#include <mutex>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <atomic>

//#include <windows.h> //windows.h中有一个宏也叫做min

//这里就不将std全部展开了，就展开几个常用的
using std::cout;
using std::endl;

static const size_t MAX_BYTES = 256 * 1024;
static const size_t NFREE_LIST = 208; //一共有208个桶，表示ThreadCache中桶的数量
static const size_t NPAGES = 129; //因为数组是从0开始映射的，那么我们就让从1下标开始
static const size_t PAGE_SHIFT = 13;
//地址/8k就是页的起始页号，通过起始页号就可以找到对应的span
//因为一页是8k所以字节数/8k就是当前页数
#ifdef _WIN32
#include <windows.h>
#elif _WIN64
#else
#endif

//此时是如果是32位机器那么就只会定义32，但是如果是x64的机器就会即定义32也定义64，所以要将64放到前面
#ifdef _WIN64
typedef unsigned long long PAGE_ID;
#elif _WIN32
typedef size_t PAGE_ID;
#endif

//最开始的时候都没有空间，那么page cache就直接找堆要空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32	
	void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#elif
	//linux下使用brk mmap等
#endif

	if (ptr == nullptr)
		throw std::bad_alloc();

	return ptr;
}

inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	// sbrk unmmap
#endif
}

//此处定义一个函数用来取内存的前四个字节，也就是当前链表中该节点的下一个节点的地址
static void*& NextObj(void* obj)
{ //这里使用引用返回可以直接对obj进行修改
	return (*(void**)obj);
}

//管理切分好的小对象的自由链表,该自由链表存储的是将大块空间分割后的小块空间
class FreeList //因为不止threadCathe需要用，后面的其他Cathe也要用，所以就放到统一头文件中
{
public:
	void push(void* obj)
	{ //插入对象
		assert(obj);
		//使用头插
		NextObj(obj) = _freeList;
		_freeList = obj;

		++_size; //链表中元素的个数
	}

	//插入一段区间
	void pushRange(void* start , void* end , size_t n)
	{
		//那么就让这段区间头茬进freeList中
		NextObj(end) = _freeList;
		_freeList = start;
		_size += n;
	}

	//将一段区间从链表中删除出来
	void popRange(void*& start, void*& end, size_t n)
	{ //start和end作为输出型参数
		assert(_size >= n);
		start = _freeList;
		end = start;
		/*int i = 0;
		void* cur = start;
		while (cur)
		{
			cur = NextObj(cur);
			i++;
		}
		if (i != n)
		{
			int x = 0;
		}*/

		for (size_t i = 0; i < n - 1; i++)
		{
			end = NextObj(end);
		}

		

		_freeList = NextObj(end);
		NextObj(end) = nullptr;
		_size -= n;
	}

	void* pop()
	{ // 弹出对象
		assert(_freeList);
		//使用头删
		void* next = NextObj(_freeList);
		void* cur = _freeList;
		_freeList = next;
		--_size;
		return cur;
	}

	size_t Size()
	{
		return _size; 
	}

	bool Empty()
	{
		return _freeList == nullptr;
	}

	//这里要传引用返回，也就是可以修改返回值
	size_t& MaxSize()
	{
		return _maxSize;
	}

private:
	void* _freeList = nullptr;
	size_t _maxSize = 1;
	size_t _size = 0; //用来记录数据的个数
};

//计算对象大小的对齐映射规则
class SizeClass
{
public:
	// 整体控制在最多10%左右的内碎片浪费 
	//比如如果是129字节，那么就按照16字节对齐之后需要向上取整到144，浪费了15个字节，15/144约等于10%，所以最多就有10%的内存碎片
	// [1,128] 8byte对齐       freelist[0,16) 这里需要16个桶，这样就可以大大减少桶的数量
	// [128+1,1024] 16byte对齐   freelist[16,72) 这里需要56个桶
	// [1024+1,8*1024] 128byte对齐   freelist[72,128) 
	// [8*1024+1,64*1024] 1024byte对齐     freelist[128,184) 
	// [64*1024+1,256*1024] 8*1024byte对齐   freelist[184,208)

	//此函数是用来表示应该开辟的空间的大小,根据对齐规则进行开辟空间
	static inline size_t _RoundUp(size_t size, size_t AlignNum)
	{ //这里定义一个子函数
		//size_t alignSize;
		//if (size % AlignNum != 0)
		//{ //此时表示当前需要处理对齐
		//	//此时处理方式就是让size除上对应的对齐的字节，让其向上取整然后再乘上对齐的字节
		//	alignSize = (size / AlignNum + 1) * AlignNum;
		//}

		//else
		//{ //此时不需要处理对齐直接就让其等于size就可以了
		//	alignSize = size;
		//}

		//return alignSize;

		return ((size + AlignNum - 1) & ~(AlignNum - 1));
		//此处也可以直接些上面的这行语句来对齐
	}

	//因为该函数没有使用什么this指针来调用成员函数，所以这里将该函数变为静态内联函数
	static inline size_t RoundUp(size_t size)
	{
		if (size <= 128) //此时按照八字节对齐
		{
			return _RoundUp(size, 8);
		}

		else if (size <= 1024) //此时按照十六字节对齐
		{
			return _RoundUp(size, 16);
		}

		else if (size <= 8 * 1024)
		{
			return _RoundUp(size, 128);
		}

		else if (size <= 64 * 1024)
		{
			return _RoundUp(size, 1024);
		}

		else if (size <= 256 * 1024)
		{
			return _RoundUp(size, 8 * 1024);
		}

		else
		{ //此时申请空间大于256KB的时候就按照1页的空间对齐，也就是8K
			return _RoundUp(size, 1 << PAGE_SHIFT);
		}
	}

	//定位桶的位置
	static inline size_t _Index(size_t bytes, size_t alignNum)
	{
		if (bytes % alignNum == 0)
		{
			return bytes / alignNum - 1; //此时因为从0号桶开始
		}
		else
		{
			return bytes / alignNum;
		}

		//此处的align_shift表示的是指数
		//return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
	}

	//计算映射的哪一个自由链表桶
	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);

		//每个区间有多少个桶，比如8kB的有16个桶
		static int group_array[4] = { 16, 56, 56, 56 };
		if (bytes <= 128)
		{
			return _Index(bytes, 8);
		}

		else if (bytes <= 1024)
		{
			return _Index(bytes - 128, 16) + group_array[0];
		}

		else if (bytes <= 8 * 1024)
		{
			return _Index(bytes - 1024, 128) + group_array[1] + group_array[0];
		}

		else if (bytes <= 64 * 1024)
		{
			return _Index(bytes - 8 * 1024, 1024) + group_array[2] + group_array[1] + group_array[0];
		}

		else if (bytes <= 256 * 1024)
		{
			return _Index(bytes - 64 * 1024, 8096) + group_array[3] + group_array[2] + group_array[1] + group_array[0];
		}

		else
		{
			assert(false);
		}

		return -1;
	}

	//一次从thread cache从中心缓存获取多少个对象
	static size_t NumMoveSize(size_t size)
	{
		assert(size > 0);
		if (size == 0) return 0;

		//此时就让一个最大字节数除以此时我们要取的桶对应的字节数
		//如果取的桶对应的字节数比较大，那么取出来的数量就比较少
		//如果取的桶对应的字节数比较小，那么取出来的数量就比较多
		int num = MAX_BYTES / size;
		if (num < 2) num = 2;

		if (num > 512) num = 512;

		return num;
	}

	//从PageCache中拿取多少个页
	static size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size);
		size_t npage = num * size; //此处表示一共需要多少个字节

		npage >>= PAGE_SHIFT; //需要的字节数和页数之间的关系是8k的关系，页数乘以8k就是字节数
		if (npage == 0) npage = 1;

		return npage;
	}

private:

};

//管理一个或者多个连续页的大块内存跨度结构
struct Span
{
	//要根据机器的型号来确定_pageId的类型
	PAGE_ID _pageId = 0; //大块内存的起始页的页号,页号是用来表示当前页的起始位置
	size_t _n = 0; //页的数量
		
	//双向链表用来存储span对象
	Span* _next = nullptr; //用于将每个span对象通过双向链表进行连接
	Span* _prev = nullptr;

	size_t _objSize = 0; //表示切好的小对象的大小，用来去掉size参数
	size_t _useCount = 0; //切好的小块内存被分配给threadCache的计数，等分配的所有内存块都被收回了，那么就将该块span返回给上层
	void* _freeList = nullptr; //将切好的小块内存连接起来

	bool _isUse = false; //表示是否被使用
};


//定义一个带头双向循环链表
class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}

	Span* begin()
	{
		return _head->_next;
	}

	Span* end()
	{
		return _head;
	}

	bool Empty()
	{
		return _head->_next == _head;
	}

	void push_front(Span* span)
	{
		Insert(begin(), span);
	}

	Span* pop_front()
	{
		Span* front = _head->_next;
		Erase(front); //此处删除并没有delete空间
		return front; 
	}

	//插入Span操作
	void Insert(Span* pos, Span* newSpan)
	{ //在pos位置的前面插入一个newSpan
		assert(pos);
		assert(newSpan);

		Span* pre = pos->_prev;
		pre->_next = newSpan;
		newSpan->_prev = pre;
		pos->_prev = newSpan;
		newSpan->_next = pos;
	}

	void Erase(Span* pos)
	{ //删除pos位置
		assert(pos);
		assert(pos != _head); //删除位置不能是哨兵位的头节点
		//1. 条件断点 , 然后通过调试栈帧的方式就可以找到上一步调用该函数的语句，依次向上找错误
		/*if (pos == _head)
		{
			int x = 0;
		}*/

		Span* prev = pos->_prev;
		Span* next = pos->_next;
		prev->_next = next;
		next->_prev = prev; 
		//注意这里不要吧pos位置的内存删除掉，此处的删除只是相当于把当前的页从链表中拿出来
		//将其还给下层的PageCache
	}

private:
	Span* _head;
public:
	std::mutex _mtx; //创建一个桶锁，也就是只有当两个线程去一个桶中取内存或者换内存的时候
	//才会执行锁操作
};